package medium;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Supplier;
import java.util.stream.Stream;

/**
 * Created by daodao on 2017/12/13.
 * Problem 17
 * Description: Given a digit string, return all possible letter combinations that the number could represent.
 * A mapping of digit to letters (just like on the telephone buttons) is given below.
 *
 * Example: Input: Digit string "23"
 *          Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 *
 * Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
 */
public class LetterCombinationsOfAPhoneNumber {
    public static List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<>();
        if (digits == null || digits.trim().equals("")) {
            return combinations;
        }
        Map<String, String[]> mapper = new HashMap<>();
        mapper.put("2", new String[]{"a", "b", "c"});
        mapper.put("3", new String[]{"d", "e", "f"});
        mapper.put("4", new String[]{"g", "h", "i"});
        mapper.put("5", new String[]{"j", "k", "l"});
        mapper.put("6", new String[]{"m", "n", "o"});
        mapper.put("7", new String[]{"p", "q", "r", "s"});
        mapper.put("8", new String[]{"t", "u", "v"});
        mapper.put("9", new String[]{"w", "x", "y", "z"});
        List<String[]> candidates = new ArrayList<>();
        for (int i = 0; i < digits.length(); i++) {
            if (mapper.containsKey(digits.substring(i, i + 1))) {
                candidates.add(mapper.get(digits.substring(i, i + 1)));
            }
        }
        if (!candidates.isEmpty()) {
            List<String> temp = combinations;
            for (int j = 0; j <candidates.size(); j++) {
                temp = combine(candidates.get(j), temp);
            }
            combinations = temp;
        }
        return combinations;
    }
    private static List<String> combine(String[] candidates, List<String> combinations) {
        List<String> newCombinations = new ArrayList<>();
        for (String letter : candidates) {
            if (combinations == null || combinations.size() == 0) {
                newCombinations.add(letter);
            } else {
                for (String oldCombination : combinations) {
                    newCombinations.add(oldCombination + letter);
                }
            }
        }
        return newCombinations;
    }
}
